package algorithm.dynamic;

/**
 * leetcode: https://leetcode.com/problems/counting-bits/
 * Difficulty : Medium
 * Topic: Dynamic Programing, Bit Manipulation
 *
 * 描述：给一个非负整数，在 [0,num] 范围的整数列表中，计算每一个整数二进制中1的个数
 * 要求：时间复杂度O(n), 空间复杂度O(n)
 *
 * Created by yzy on 2020-03-31 19:03
 */
public class CountingBits {

    /**
     * Runtime: 1ms faster than 99.42%
     * Memory: 43.2MB, less than 5.88%
     *
     * 思路：
     * 动态规划
     * 举栗：
     * 按二进制来看，num = 1011 (11)
     * 那么 f[1011] = f[101] + (1011 & 1)
     * 也就是，前[n-1]位里1的个数 + 最后一位1的个数。
     * 因为 前[n-1]位1的个数已经求出来，所以可以使用之前的计算结果。
     * @param num
     * @return
     */
    public int[] countBits(int num) {
        int[] f = new int[num+1];
        for(int i=1; i<=num; i++){
            f[i] = f[i >> 1] + (i&1);
        }
        return f;
    }
}
